﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Roton.Memory
{
    class Heap
    {
        // Heap entries are stored in a dictionary. Duplicates are allowed
        // and in fact are needed for proper implementation. NextEmpty will
        // always contain the lowest index for the next addition.

        // In real operation, the index would actually be a pointer. However,
        // such pointers are not needed in a managed programming language.

        private Dictionary<int, byte[]> heapEntries;
        private int nextEmpty = 0;

        public Heap()
        {
            heapEntries = new Dictionary<int, byte[]>();
            Clear();
        }

        /// <summary>
        /// Add data to the heap and return its index.
        /// </summary>
        /// <param name="value">Heap data to add.</param>
        /// <returns>The heap index for the added data.</returns>
        public int Add(byte[] value)
        {
            int result = nextEmpty;
            heapEntries.Add(nextEmpty, value);
            while (heapEntries.ContainsKey(nextEmpty))
                nextEmpty++;
            return result;
        }

        /// <summary>
        /// Clear the heap.
        /// </summary>
        public void Clear()
        {
            heapEntries.Clear();
            nextEmpty = 0;
        }

        /// <summary>
        /// Remove data from a heap.
        /// </summary>
        /// <param name="index">Index of the heap data to remove.</param>
        public void Remove(int index)
        {
            if (heapEntries.ContainsKey(index))
            {
                heapEntries.Remove(index);
                if (nextEmpty > index)
                    nextEmpty = index;
            }
        }

        /// <summary>
        /// The total size of the heap, in bytes.
        /// </summary>
        public int Size
        {
            get
            {
                int result = 0;
                foreach (KeyValuePair<int, byte[]> entry in heapEntries)
                    result += entry.Value.Length;
                return result;
            }
        }
    }
}
